# 有 n 个城市通过一些航班连接。给你一个数组 flights ，
# 其中 flights[i] = [fromi, toi, pricei] ，表示该航班都从城市 fromi 开始，以价格 pricei 抵达 toi。
#  现在给定所有的城市和航班，以及出发城市 src 和目的地 dst，你的任务是找到出一条最多经过 k 站中转的路线，使得从 src 到 dst 的 价格最便
# 宜 ，并返回该价格。 如果不存在这样的路线，则输出 -1。
#
#  示例 1：
# 输入:
# n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
# src = 0, dst = 2, k = 1
# 输出: 200
#
#  示例 2：
# 输入:
# n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
# src = 0, dst = 2, k = 0
# 输出: 500
import collections
from typing import List


class Solution:
    def findCheapestPrice3(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
        """
        Bellman-Ford算法的变形(松弛K + 1次)
        :param n:
        :param flights:
        :param src:
        :param dst:
        :param k:
        :return:
        """
        inf = 1 << 30
        minPrices = [inf] * n  # minPrices[i] 表示src到i到最小价格
        minPrices[src] = 0
        for _ in range(k + 1):  # k+1 次松弛
            cp = minPrices.copy()  # 保证最短距离是上一步的
            for fromm, to, price in flights:
                minPrices[to] = min(cp[fromm] + price, minPrices[to])
        return minPrices[dst] if minPrices[dst] < inf else -1

    def findCheapestPrice2(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
        """
        bfs + 剪枝
        :param n:
        :param flights:
        :param src:
        :param dst:
        :param k:
        :return:
        """
        adjList = self.getAdjList(flights)
        queue = collections.deque()
        minPrices = [float('inf')] * n  # minPrices[i] 表示src到i到最小价格
        k += k
        queue.append((0, src))
        while queue and k:
            layerSize = len(queue)
            for _ in range(layerSize):
                curTotalPrice, tmpNode = queue.popleft()
                for v, price in adjList[tmpNode]:
                    tmpPathPrice = curTotalPrice + price
                    # 小于 v 之前记录的最小值，且小于 dst 之前记录的最小值(剪枝1)
                    if tmpPathPrice < minPrices[v] and tmpPathPrice < minPrices[dst]:
                        minPrices[v] = tmpPathPrice
                        if v != dst:  # 到达了dst,就不需要再进行遍历(剪枝2)
                            queue.append((tmpPathPrice, v))
            k -= 1
        return minPrices[dst] if minPrices[dst] < float('inf') else -1

    def findCheapestPrice1(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
        """
        回溯(dfs) 超时
        找出所有能够经过 K 中转就到达 dst 的路径和
        然后返回最小值
        :param n:
        :param flights:
        :param src:
        :param dst:
        :param k:
        :return:
        """
        adjList = self.getAdjList(flights)
        prices = []

        def backTrace(pathPrice: int, start: int, k: int, visited: List[bool]) -> None:
            if start == dst and k > 0:
                prices.append(pathPrice)
            for v, price in adjList[start]:
                if k > 0:
                    if not visited[v]:
                        visited[v] = True
                        pathPrice += price
                        k -= 1
                        backTrace(pathPrice, v, k, visited)
                        k += 1
                        pathPrice -= price
                        visited[v] = False
                else:
                    return

        backTrace(0, src, k + 2, visited=[False] * n)
        return min(prices) if len(prices) else -1

    def getAdjList(self, flights: List[List[int]]) -> dict:
        adjList = collections.defaultdict(list)
        for fromm, to, price in flights:
            adjList[fromm].append((to, price))
        return adjList

    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
        return self.findCheapestPrice3(n, flights, src, dst, k)


if __name__ == "__main__":
    n, src, dst, k = 3, 0, 2, 0
    edges = [[0, 1, 100], [1, 2, 100], [0, 2, 500]]
    # n, src, dst, k = 3, 0, 2, 1
    # edges = [[0, 1, 100], [1, 2, 100], [0, 2, 500]]

    # edges = [[1, 2, 10], [2, 0, 7], [1, 3, 8], [4, 0, 10], [3, 4, 2], [4, 2, 10], [0, 3, 3], [3, 1, 6], [2, 4, 5]]
    # n, src, dst, k = 5, 0, 4, 1

    # edges = [[0,12,28],[5,6,39],[8,6,59],[13,15,7],[13,12,38],[10,12,35],[15,3,23],
    #             [7,11,26],[9,4,65],[10,2,38],[4,7,7],[14,15,31],[2,12,44],[8,10,34],
    #             [13,6,29],[5,14,89],[11,16,13],[7,3,46],[10,15,19],[12,4,58],[13,16,11],
    #             [16,4,76],[2,0,12],[15,0,22],[16,12,13],[7,1,29],[7,14,100],[16,1,14],
    #             [9,6,74],[11,1,73],[2,11,60],[10,11,85],[2,5,49],[3,4,17],[4,9,77],[16,3,47],
    #             [15,6,78],[14,1,90],[10,5,95],[1,11,30],[11,0,37],[10,4,86],[0,8,57],[6,14,68],
    #             [16,8,3],[13,0,65],[2,13,6],[5,13,5],[8,11,31],[6,10,20],[6,2,33],[9,1,3],[14,9,58],
    #             [12,3,19],[11,2,74],[12,14,48],[16,11,100],[3,12,38],[12,13,77],[10,9,99],[15,13,98],
    #             [15,12,71],[1,4,28],[7,0,83],[3,5,100],[8,9,14],[15,11,57],[3,6,65],[1,3,45],[14,7,74],
    #             [2,10,39],[4,8,73],[13,5,77],[10,0,43],[12,9,92],[8,2,26],[1,7,7],[9,12,10],[13,11,64],
    #             [8,13,80],[6,12,74],[9,7,35],[0,15,48],[3,7,87],[16,9,42],[5,16,64],[4,5,65],[15,14,70],
    #             [12,0,13],[16,14,52],[3,10,80],[14,11,85],[15,2,77],[4,11,19],[2,7,49],[10,7,78],[14,6,84],
    #             [13,7,50],[11,6,75],[5,10,46],[13,8,43],[9,10,49],[7,12,64],[0,10,76],[5,9,77],[8,3,28],[11,9,28],
    #             [12,16,87],[12,6,24],[9,15,94],[5,7,77],[4,10,18],[7,2,11],[9,5,41]]
    # n, src, dst, k = 17, 13, 4, 13

    # edges = [[0,1,100],[0,2,100],[0,3,10],[1,2,100],[1,4,10],[2,1,10],[2,3,100],[2,4,100],[3,2,10],[3,4,100]]
    # n, src, dst, k = 5, 0, 4, 3
    print(Solution().findCheapestPrice(n, edges, src, dst, k))
